package tree

type node[K comparable] interface {
	KeyID() K
	ParentKeyID() K
}

// AddChild 函数示例
// func (c *ClassInfo) AddChild(item T) error {
// 	itemDiv.Parent = c
// 	insertPos := -1
// 	if c.Children != nil {
// 		for n, child := range c.Children {
// 			if child.Code > itemDiv.Code {
// 				insertPos = n
// 				break
// 			}
// 		}
// 	}
// 	if insertPos == -1 {
// 		c.Children = append(c.Children, itemDiv)
// 	} else {
// 		rear := append([]*ClassInfo{itemDiv}, c.Children[insertPos:]...)
// 		c.Children = append(c.Children[:insertPos], rear...)
// 	}
// 	return nil
// }

type nodeWrap[K comparable, T node[K]] struct {
	node  T
	index int
}

// Tree 树状组织生成
type Tree[K comparable, T node[K]] struct {
	TopNodes []T
	Nodes    []T
	nodeMap  map[K]*nodeWrap[K, T]
	addChild func(parent, child T)
}

// NewTree 创建树状结构生成者
func NewTree[K comparable, T node[K]](fnAddChild func(parent, child T)) *Tree[K, T] {
	tree := &Tree[K, T]{
		nodeMap:  map[K]*nodeWrap[K, T]{},
		addChild: fnAddChild,
	}
	return tree
}

type SameKeyOperator int

const (
	SKOReplace SameKeyOperator = iota
	SKOIgnoreThis
	SKOReturnIndex
)

// AddItem 添加项目
// replaceSameID == true 时
//	永远返回 -1
// replaceSameID == false 时
// 	返回 -1 添加完成
// 	返回值大于等于 0， ID 与 这个索引值的元素重复
func (t *Tree[K, T]) AddItem(item T, whileSameKey SameKeyOperator) int {
	nw, got := t.nodeMap[(item).KeyID()]
	if got {
		if whileSameKey == SKOReturnIndex {
			return nw.index
		}
		if whileSameKey == SKOReplace {
			nw.node = item
			t.Nodes[nw.index] = item
			return -1
		}
		// SKOIgnoreThis 忽略
		return -1
	}
	t.nodeMap[(item).KeyID()] = &nodeWrap[K, T]{node: item, index: len(t.Nodes)}
	t.Nodes = append(t.Nodes, item)
	return -1
}

// FindNode 在树中查找节点
func (t *Tree[K, T]) GetNode(id K) (T, bool) {
	item, exists := t.nodeMap[id]
	if !exists {
		var t T
		return t, false
	}
	return item.node, true
}

// Generate 生成树
func (t *Tree[K, T]) Generate() {
	for _, node := range t.Nodes {
		// 定位父节点
		var parent *nodeWrap[K, T]
		var ok bool
		parent, ok = t.nodeMap[(node).ParentKeyID()]
		if !ok {
			// 作为 顶级节点
			t.TopNodes = append(t.TopNodes, node)
		} else {
			// 插入到父节点的 children 中
			t.addChild(parent.node, node)
		}
	}
}
